Field programmable gate arrays (FPGAs) are known as programmable logic devices which offer higher densities than any other programmable logic devices. The architecture of FPGAs is array based. The entire device is constituted of a two-dimensional array of programmable logic blocks that can be interconnected via horizontal and vertical routing channels. The programmable logic blocks are look-up tables (LUTs) grouped into pairs or trios and provided with flip-flops. LUTs can be configured to perform one-output Boolean functions and therefore can be used to map any type of logic gate. The mapping process involves the transformation of the gate to its truth table. The truth table specifies for which input combinations the gate delivers a logic one, and for which input combinations the gate delivers a logic zero. The gate truth table is stored in the LUT: each entry in the truth table is stored in one entry of the LUTs. Therefore, to store the truth table of a n-input gate, 2.sup.n entries are needed. Usually, the number of gate inputs is limited to reasonable values, as not to provoke a combinatorial explosion in the number of LUT entries.
The horizontal and vertical routing channels in an FPGA are made of several type of tracks. Each type provides different connection capabilities, buffering capabilities and timing attributes. Both horizontal and vertical routing channels can be configured to connect any logic block to any other block or blocks in the two dimensional array. The connections are established by setting switching transistors in order to create or delete a connection. The switching transistors are grouped in two-dimensional programmable matrices, usually referred to as switch matrix (SM). The decision on how to connect a given block to another or other blocks depends on many factors. It depends on how close or how far the blocks to be connected are. It depends on how many tracks and what type of tracks are still available. It depends on how many signals are still left to be routed.
One of the major drawbacks of FPGAs is the difficulty of predicting at compile time, before the design is mapped and routed on the FPGA chip, the timing behavior and performance of the prototype. Because of the randomness of the logic block-to-LUT mapping process, it is not possible to predict the particular route a given signal will travel, and therefore, it becomes an impractical task to determine where are the critical paths, and hence to predict the timing behavior of the prototype before the design is mapped and routed. This drawback is exacerbated by the necessity to use different types of routing tracks, either in order to boost the performance of the prototype, or decrease routing congestions. Another major drawback of FPGAs, is routing congestion. The problem stems from the fact that the programmable logic blocks offer only fine granularity mapping capabilities. Only gates with a reasonable number of inputs, and with only one output can be mapped to logic blocks. The consequence is an increase in the number of signals that have to be routed from one block to another block, a number which is directly proportional to the number of gates in the netlist of the design.